/**
 * @brief 顺序表模板类
 * @version 1.0
 * @author TMJ
 * @date 2023-12-22
 */

#ifndef LINEAR_TABLE_SEQ_LIST_H
#define LINEAR_TABLE_SEQ_LIST_H

#include <stdexcept>
#include <iostream>
#include "linear_list.h"

// 顺序表模板类
template<typename type>
class SeqList
        : public LinearList<type> {
public:

    // 默认构造函数
    SeqList() : _data(nullptr), _capacity(0), _length(0) {}

    // 指定容量大小的构造函数
    explicit SeqList(int capacity = 100);

    // 拷贝构造函数
    SeqList(const SeqList<type>& srcList);

    // 析构函数
    ~SeqList();

    // 获取容量
    int getCapacity() const;

    // 获取当前大小
    int getLength() const;

    // 搜索
    int search(const type& data) const;

    // 获取结点数据
    bool getData(int pos, type& data) const;

    // 设置结点数据
    bool setData(int pos, const type& data) const;

    // 插入结点
    bool insertData(int pos, const type& data);

    // 删除结点
    bool removeData(int pos, type& data);

    // 是否为空
    bool isEmpty() const;

    // 是否满了
    bool isFull() const;

    // 重置容量
    bool resetCapacity(int capacity);

    // 打印
    void print();


private:

    type *_data;    // 数据项数组
    int _capacity;  // 容量
    int _length;    // 大小
};

// 指定容量大小的构造函数
template<typename type>
SeqList<type>::SeqList(int capacity) {

    // 非法性检测
    if (capacity <= 0) {
        throw std::out_of_range("capacity <= 0");
    }

    this->_capacity = capacity;
    this->_length = 0;
    this->_data = new type[capacity];
    if (!this->_data) {
        throw std::bad_alloc();
    }
}

// 拷贝构造函数
template<typename type>
SeqList<type>::SeqList(const SeqList<type> &srcList) {
    this->_capacity = srcList._capacity;
    this->_length = srcList._length;

    if (this->_capacity == 0) {
        return;
    }

    this->_data = new type[this->_capacity];
    if (!this->_data) {
        throw std::bad_alloc();
    }

    // 数据拷贝
    for (int index = 0; index < this->_length; ++index) {
        this->_data[index] = srcList._data[index];
    }
}

// 析构函数
template<typename type>
SeqList<type>::~SeqList() {
    delete[] this->_data;
}

// 获取容量
template<typename type>
int SeqList<type>::getCapacity() const {
    return this->_capacity;
}

// 获取大小
template<typename type>
int SeqList<type>::getLength() const {
    return this->_length;
}

// 搜索指定元素
template<typename type>
int SeqList<type>::search(const type &data) const {
    for (int index = 0; index < this->_length; ++index) {
        if (this->_data[index] == data) {
            return index + 1;
        }
    }
    return 0;
}

// 获取指定位置的元素
template<typename type>
bool SeqList<type>::getData(int pos, type &data) const {
    // 非法性检测
    if (pos <= 0 || pos > this->_length) {
        return false;
    }

    data = this->_data[pos - 1];

    return true;
}

// 设置指定位置的元素
template<typename type>
bool SeqList<type>::setData(int pos, const type &data) const {
    // 非法性检测
    if (pos <= 0 || pos > this->_length) {
        return false;
    }

    this->_data[pos - 1] = data;

    return true;
}

// 在指定位置插入元素
template<typename type>
bool SeqList<type>::insertData(int pos, const type &data) {
    // 非法性检测
    if (pos < 0 || pos > this->_length + 1) {
        return false;
    }

    // 动态扩容
    if (this->isFull()) {
        int newCapacity = this->_length * 2;
        type *newData = new type[newCapacity];

        for (int i = 0; i < this->_length; ++i) {
            newData[i] = this->_data[i];
        }

        delete[] this->_data;
        this->_data = newData;
        this->_capacity = newCapacity;
    }

    // 插入元素
    for (int i = this->_length - 1; i >= pos - 1; --i) {
        this->_data[i + 1] = this->_data[i];
    }

    this->_data[pos - 1] = data;
    this->_length++;

    return true;
}

// 删除指定位置的元素
template<typename type>
bool SeqList<type>::removeData(int pos, type &data) {
    // 非法性检测
    if (this->isEmpty() || pos <= 0 || pos > this->_length) {
        return false;
    }

    data = this->_data[pos - 1];
    for (int i = pos; i < this->_length; i++) {
        this->_data[i - 1] = this->_data[i];
    }
    this->_length--;

    return true;
}

// 判断是否为空
template<typename type>
bool SeqList<type>::isEmpty() const {
    if (this->_length == 0)
        return true;
    return false;
}

// 判断是否满了
template<typename type>
bool SeqList<type>::isFull() const {
    if (this->_length == this->_capacity)
        return true;
    return false;
}

// 重置容量
template<typename type>
bool SeqList<type>::resetCapacity(int capacity) {
    // 非法性检测
    if (capacity < 0) {
        return false;
    }

    // 等于原来的容量
    if (capacity == this->_capacity) {
        return true;
    }

    type *newData = new type[capacity];

    // 大于原来的容量
    if (capacity > this->_capacity) {
        for (int i = 0; i < this->_length; ++i) {
            newData[i] = this->_data[i];
        }
    }

    // 小于原来的容量
    if (capacity < this->_capacity) {
        if (capacity >= this->_length) {
            for (int i = 0; i < this->_length; ++i) {
                newData[i] = this->_data[i];
            }
        } else {
            for (int i = 0; i < capacity; ++i) {
                newData[i] = this->_data[i];
            }
            this->_length = capacity;
        }
    }

    delete[] this->_data;
    this->_data = newData;
    this->_capacity = capacity;

    return true;
}

template<typename type>
void SeqList<type>::print() {
    for (int i = 0; i < this->_length; ++i) {
        std::cout << this->_data[i] << " ";
    }
    std::cout << std::endl;
}

#endif //LINEAR_TABLE_SEQ_LIST_H
